package main.leetcode.clockin.October;

/**
 * 416. 分割等和子集
 *
 * <p>给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * <p>注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
 *
 * <p>示例 1: <br>
 * 输入: [1, 5, 11, 5] <br>
 * 输出: true <br>
 * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
 *
 * <p>示例 2: <br>
 * 输入: [1, 2, 3, 5] <br>
 * 输出: false <br>
 * 解释: 数组不能分割成两个元素和相等的子集.
 */
public class day11 {
    //    public static void main(String[] args) {
    //        System.out.println(new day11().canPartition(new int[] {1, 5, 11, 5}));
    //        System.out.println(new day11().canPartition(new int[] {1, 2, 3, 5}));
    //    }

    //    public boolean canPartition(int[] nums) {
    //        int sum = 0;
    //        for (int num : nums) {
    //            sum += num;
    //        }
    //        if ((sum & 1) == 1) {
    //            return false;
    //        }
    //        sum /= 2;
    //        return backtrack(nums, sum, 0, 0);
    //    }

    //    /** 回溯 tle */
    //    public boolean canPartition(int[] nums) {
    //        int sum = 0;
    //        for (int num : nums) {
    //            sum += num;
    //        }
    //        if ((sum & 1) == 1) {
    //            return false;
    //        }
    //        sum /= 2;
    //        return backtrack(nums, sum, 0, 0);
    //    }
    //
    //    private boolean backtrack(int[] nums, int tar, int cur, int index) {
    //        if (cur == tar) {
    //            return true;
    //        }
    //        if (cur > tar || index == nums.length) {
    //            return false;
    //        }
    //        return backtrack(nums, tar, cur + nums[index], index + 1)
    //                || backtrack(nums, tar, cur, index + 1);
    //    }
}
